package a2022.a20221009;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author lenovo
 * @date 2022/10/9
 */
public class a {
    public static void main(String[] args) {
        //
        System.out.println(scoreOfParentheses("(()(()))"));
        System.out.println(scoreOfParentheses2("(())((()))"));
        System.out.println(scoreOfParentheses3("(())((()))"));

    }

    public static int scoreOfParentheses(String s) {
        int length = s.length();
        if (length == 2) return 1;
        int num = 0, len = 0;
        for (int i = 0; i < length; i++) {
            num += (s.charAt(i) == '(' ? 1 : -1);
            if (num == 0) {
                len = i + 1;
                break;
            }
        }
        if(len == length){
            return 2 * scoreOfParentheses(s.substring(1, length - 1));
        }else {
            return scoreOfParentheses(s.substring(0, len)) + scoreOfParentheses(s.substring(len));
        }
    }

    public static int scoreOfParentheses2(String s) {
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        for (char c : s.toCharArray()) {
            if (c == '(') d.addLast(0);
            else {
                int cur = d.pollLast();
                d.addLast(d.pollLast() + Math.max(cur * 2 , 1));
            }
        }
        return d.peekLast();
    }


    public static int scoreOfParentheses3(String s) {
        int bal = 0, n = s.length(), res = 0;
        for (int i = 0; i < n; i++) {
            bal += (s.charAt(i) == '(' ? 1 : -1);
            if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') {
                res += 1 << bal;
            }
        }
        return res;
    }


}
